/* 归并排序 */
#include <stdio.h>
#include "public.h"

int main(){

    //定义无序数组
    int arr[] = {5,6,9,1,3,2,7,8,4,0};
    int len = sizeof(arr)/4;

    //定义等长数组
    int* tarr = malloc(sizeof(arr));

    //输出原始数组
    each(arr,len);
    //定义执行次数
    int count = 0;
    //最小处理单元为2，逐渐翻倍到大于数组长度则停止
    int sz = 1;
    do{

        sz *= 2;

        int* a = arr;
        int* b = tarr;

        //根据执行次数判断归并方向
        if(count++%2==1){
            a = tarr;
            b = arr;
        }

        //从a归并到b
        int index = 0;
        for(int i = 0; i < len; i += sz){
            
            int ai = i,bi = i + sz / 2;
            while(ai < i + sz / 2 && bi < len && bi < i + sz){
                b[index++] = a[ai] < a[bi] ? a[ai++] : a[bi++];
            }

            while(ai < i + sz / 2){
                b[index++]=a[ai++];
            }

            while(bi < len && bi < i + sz){
                b[index++]=a[bi++];
            }
        }

        //输出每次调整结果
        each(b,len);

    }while (sz <= len);
    
}